package astudy.tree.impl;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 
 * 非递归方式实现二叉树遍历
 * 
 * @author wong.tong@gmail.com
 *
 */
@SuppressWarnings("unchecked")
public class Iterator {

	private Iterator() {}
	
	/**
	 * 先序遍历
	 * @param root
	 * @return
	 */
	public static List<BinaryTreeNode> preOrder(BinaryTreeNode root) {
		
		List<BinaryTreeNode> list = new ArrayList<BinaryTreeNode>();
		LinkedList<BinaryTreeNode> stack = new LinkedList<BinaryTreeNode>();
		stack.push(root);
		
		BinaryTreeNode cur = null;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			list.add(cur);
			if (cur.getRight() != null) {
				stack.push(cur.getRight());
			}
			if (cur.getLeft() != null) {
				stack.push(cur.getLeft());
			}
		}
		return list;
	}
	
	/**
	 * 中序遍历
	 * @param root
	 * @return
	 */
	public static List<BinaryTreeNode> midOrder(BinaryTreeNode root) { 
		
		List<BinaryTreeNode> list = new ArrayList<BinaryTreeNode>();
		LinkedList<BinaryTreeNode> stack = new LinkedList<BinaryTreeNode>();
		BinaryTreeNode cur = root;
		while (true) {
			while (cur != null) {
				stack.push(cur);
				cur = cur.getLeft();
			}
			if (!stack.isEmpty()) {
				cur = stack.pop();
				list.add(cur);
				cur = cur.getRight();
			} else {
				break;
			}
		}
		return list;
	}
	
	public static List<BinaryTreeNode> midOrder2(BinaryTreeNode root) { 
		
		List<BinaryTreeNode> list = new ArrayList<BinaryTreeNode>();
		LinkedList<BinaryTreeNode> stack = new LinkedList<BinaryTreeNode>();
		stack.push(root);
		LinkedList<Integer> flags = new LinkedList<Integer>();
		flags.push(0);
		
		BinaryTreeNode cur = null;
		int flag = -1;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			flag = flags.pop();
			if (flag == 0) {
				stack.push(cur);
				flags.push(1);
				if (cur.getLeft() != null) {
					stack.push(cur.getLeft());
					flags.push(0);
				}
			} else {	//flag = 1
				list.add(cur);
				if (cur.getRight() != null) {
					stack.push(cur.getRight());
					flags.push(0);
				}
			}
		}
		return list;
	}	

	/**
	 * 后序遍历
	 * @param root
	 * @return
	 */
	public static List<BinaryTreeNode> postOrder(BinaryTreeNode root) { 
		
		LinkedList<BinaryTreeNode> stack = new LinkedList<BinaryTreeNode>();
		stack.push(root);
		LinkedList<Integer> flags = new LinkedList<Integer>();
		flags.push(0);

		List<BinaryTreeNode> list = new ArrayList<BinaryTreeNode>();
		BinaryTreeNode cur = null;
		int flag = -1;
		while (!stack.isEmpty()) {
			cur = stack.pop();
			flag = flags.pop();
			if (flag == 0) {
				stack.push(cur);
				flags.push(1);
				if (cur.getRight() != null) {
					stack.push(cur.getRight());
					flags.push(0);
				}
				if (cur.getLeft() != null) {
					stack.push(cur.getLeft());
					flags.push(0);
				}
			} else {	// flag == 1
				list.add(cur);
			}
		}
		return list;
	}

}